// https://leetcode-cn.com/problems/combination-sum/
// 输入一个数组 和一个目标数 返回 可能的组合 这是一个特征明显的回溯问题
// 回溯问题的思考过程是非常鲜明的:
// 1.dfs 还是 bfd
// 2.确定选择路径 结果集 状态
// 3.确定选择分支 此题是 要么选择当前数 要么不选择当前数 选择状态由索引进行控制
class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};